Focusing on the problem that the session-based provenance scheme requires that all of the provenance sessions must be received by the Base Station (BS) correctly before decoding, which decreases the robustness of the scheme, a provenance scheme with stepwise refinement was proposed. Firstly, a large Wireless Sensor Network (WSN) topology was divided into different granularities which were composed of a series of abstract nodes through quotient space dividing theory. Then, the dictionary based provenance scheme was used to transmit provenance at different grained layers. Therefore, the BS reconstructed the provenance from the coarse-grained layer to the fine-grained one as well as judged whether to discard the data or not according to the results of the coarse-grained layer's decoding. The theoretical analysis, simulations and experimental results show that in comparison of the traditional provenance schemes, the average compression ratio of the proposed method is improved by 51.8%, and the energy consumption of that is reduced by 50.5%.